package course.p4_list.s2_TwoNextList;

public class DLinkedListAlgorithm {

    /**
     * 以输入节点为头，计算出链表长度
     * @param head 头节点
     * @return 链表长度
     */
    static int ListLengthByHead(Node head) {
        int length = 0;
        Node cur = head;
        while(cur!=null){
            length++;
            cur = cur.next;
        }
        return length;
    }

    /**
     * 以输入节点为尾，计算出链表长度
     * @param tail 尾节点
     * @return 链表长度
     */
    static int ListLengthByTail(Node tail) {
        int length = 0;
        Node cur = tail;
        while (cur!=null){
            length++;
            cur = cur.previous;
        }
        return length;
    }

    /**
     * 根据头节点遍历打印链表内容
     * @param headNode 链表头节点
     */
    static void toStringByHead(Node headNode) {
        Node check = headNode;
        if(check==null){
            System.out.print("null");
            return;
        }
        for(;;){
            System.out.print(check.nodeName+"<->");
            check = check.next;
            if(check == null){
                System.out.println("null");
                break;
            }
        }
    }

    /**
     * 根据尾节点打印链表内容
     * @param tailNode 链表尾节点
     */
    static void toStringByTail(Node tailNode) {
        Node check=tailNode;
        if(check==null){
            System.out.print("null");
            return;
        }
        for(;;){
            System.out.print(check.nodeName+"<->");
            check = check.previous;
            if(check == null){
                System.out.println("null");
                break;
            }
        }
    }

    /**
     * 正向插入
     * 主要思路是：
     *      先判断链表中存不存在position位置，若没有输出错误信息并返回头节点；
     *      若存在则进行插入操作：首先判断position是不是为0，因为这种情况不同于其他的。
     *      否则，先找到第position-1个节点和position个节点，将前一个节点的下一节点设为nodeToInsert
     *      将nodeToInsert的下一个节点设置为position节点，这样完成插入操作
     * @param headNode 链表头节点
     * @param nodeToInsert 要插入的节点
     * @param position 指定插入的位置
     * @return 插入后的链表头节点
     */
    static Node insertByHead(Node headNode, Node nodeToInsert, int position) {
        if(headNode==null) {
            return nodeToInsert;
        }
        //获得输入链表的长度
        int size = ListLengthByHead(headNode);
        //判断链表内是否存在此位置
        if(position > size || position < 0) {
            System.out.println("位置异常！！ position不能超过 "+size);
            return headNode;
        }
        //在链表开头插入
        if(position == 0) {
            nodeToInsert.next = headNode;
            headNode.previous = nodeToInsert;
            return nodeToInsert;
        }
        //在中间或末尾插入
        else {
            Node prev = headNode;
            int count = 0;
            //找到那个位置的前一个节点
            while(count < position-1) {
                //获得第position-1位置的节点
                prev = prev.next;
                count++;
            }
            //获得第position位置的节点
            Node currentNode = prev.next;
            // 在cur不为空的时候才进行insert和cur之间的关系改变
            if(currentNode!=null) {
                nodeToInsert.next = currentNode;
                currentNode.previous = nodeToInsert;
            }
            prev.next =nodeToInsert;
            nodeToInsert.previous = prev;
        }
        return headNode;
    }

    /**
     * 反向插入
     * @param tailNode 链表尾节点
     * @param nodeToInsert 要插入的节点
     * @param position 指定插入的位置
     * @return 插入后的链表头节点
     */
    static Node insertByTail(Node tailNode, Node nodeToInsert, int position) {
        if(tailNode == null) {
            return nodeToInsert;
        }
        //获得输入链表的实际长度
        int size = ListLengthByTail(tailNode);
        //判断链表内是否存在此位置
        if(position > size || position < 0) {
            System.out.println("位置异常！！ position不能超过 "+size);
            return tailNode;
        }
        //在链表结尾插入
        if(position == size) {
            nodeToInsert.previous = tailNode;
            tailNode.next = nodeToInsert;
            return nodeToInsert;
        }
        //在中间或开头插入
        else {
            Node previousNode = tailNode;
            int count = 0;
            //找到那个位置的前一个节点
            while(count < size-position-1) {
                //获得第position-1位置的节点
                previousNode = previousNode.previous;
                count++;
            }
            //获得第position位置的节点
            Node currentNode = previousNode.previous;
            //插入操作
            if(currentNode!=null) {
                currentNode.next = nodeToInsert;
                nodeToInsert.previous = currentNode;
            }
            nodeToInsert.next = previousNode;
            previousNode.previous = nodeToInsert;
        }
        return tailNode;
    }

    /**
     * 方法和前面的插入方法有异曲同工之妙：
     *  主要思想是找到position的前一个节点和后一个节点，然后将他们连接
     * @param headNode 头节点
     * @param position 删除的位置
     * @return 删除后的链表头节点
     */
    static Node deleteByHead(Node headNode, int position) {
        int size = ListLengthByHead(headNode);
        if(position>=size||position<0) {
            System.out.println("位置异常！！ position位置不能超过 "+(size-1));
            return headNode;
        }
        //删除表头
        if(position==0) {
            //将第二个节点的上一节点引用删除
            headNode.next.previous = null;
            return headNode.next;
        }
        //删除中间或结尾节点
        else {
            Node previousNode = headNode;
            int count = 0;
            //获得目标节点的上一个节点
            while(count < position-1) {
                previousNode = previousNode.next;
                count++;
            }
            //要删除目标节点
            Node currentNode = previousNode.next;
            previousNode.next = currentNode.next;
            if(currentNode.next!=null)
              currentNode.next.previous = previousNode;
        }
        return headNode;
    }

    /**
     * 方法和前面的插入方法有异曲同工之妙：
     *  主要思想是找到position的前一个节点和后一个节点，然后将他们连接
     * @param tailNode 尾节点
     * @param position 删除的位置
     * @return 删除后的链表头节点
     */
    static Node deleteByTail(Node tailNode, int position) {
        int size = ListLengthByTail(tailNode);
        if(position>=size||position<0) {
            System.out.println("位置异常！！ position位置不能超过 "+(size-1));
            return tailNode;
        }
        //删除表尾
        if(position == size-1) {
            tailNode.previous.next = null;
            return tailNode.previous;
        }
        //删除中间或结尾节点
        else {
            Node previousNode = tailNode;
            int count = 0;
            //获得目标节点的上一个节点
            while(count < size-position-2) {
                previousNode = previousNode.previous;
                count++;
            }
            //要删除目标节点
            Node currentNode = previousNode.previous;
            previousNode.previous = currentNode.previous;
            if(currentNode.previous!=null)
               currentNode.previous.next = previousNode;
        }
        return tailNode;
    }

    /**
     * 获取链表指定位置的元素
     * @param head
     * @param position
     * @return
     */
    static Node getByHead(Node head,int position) {
        int size = ListLengthByHead(head);
        if( position < 0 || position >= size) {
            System.out.println("链表不存在该位置： "+ position +"链表最大位置索引： "+(size-1));
            return null;
        }
        Node cur = head;
        for (int index = 0;index < position;index++){
            cur = cur.next;
        }
        return cur;
    }

    static Node getByTail(Node tail,int position) {
        int size = ListLengthByTail(tail);
        if(position<0 || position >= size){
            System.out.println("链表不存在该位置： "+ position +"链表最大位置索引： "+(size-1));
            return null;
        }
        Node cur = tail;
        for(int index = 0;index< (size-position-1);index++){
            cur = cur.previous;
        }
        return cur;
    }

}
